﻿/* Write a program that reads three integer numbers N, K and S and an array of N elements from the console. 
 * Find in the array a subset of K elements that have sum S or indicate about its absence.
*/


using System;
using System.Collections.Generic;

class NKS_Subset
{
    static void Main()
    {
        uint N;
        int K, S;

        bool iProvided = false;
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter a positive integer.");
            else iProvided = true;
            Console.Write("Enter N: ");
        } while (UInt32.TryParse(Console.ReadLine(), out N) == false || N < 1);
        
        iProvided = false; //reset iProvided
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
            else iProvided = true;
            Console.Write("Enter K: ");
        } while (Int32.TryParse(Console.ReadLine(), out K) == false);

        iProvided = false; //reset iProvided
        do
        {
            if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
            else iProvided = true;
            Console.Write("Enter S: ");
        } while (Int32.TryParse(Console.ReadLine(), out S) == false);

        iProvided = false; //reset iProvided
        int[] nums = new int[N];
        for (int i = 0; i < nums.Length; i++)
        {
            iProvided = false;
            do
            {

                if (iProvided == true) Console.WriteLine("Error! Please enter an integer.");
                else iProvided = true;
                Console.Write("Enter element {0}: ", i + 1);
            } while (Int32.TryParse(Console.ReadLine(), out nums[i]) == false);
        }
        //Console.WriteLine("{0} {1} {2}", N, K, S);


        bool found = false;
        int maxSets = (int)Math.Pow(2, nums.Length) - 1;
        int checkedNums = 0;
        List<int> subsetNums = new List<int>();
        //for (int i = 0; i < maxSets; i++) subsetNums[i] = int.MinValue; //default value
        
        for (int i = 1; i <= maxSets; i++)
        {
            long currentSum = 0;
            for (int j = 1; j <= nums.Length; j++)
            {
                if (((i >> (j - 1)) & 1) == 1)
                {
                    currentSum += nums[j - 1];
                    checkedNums++;
                    subsetNums.Add(nums[j - 1]);
                    //subsetNums[i] = nums[j - 1];
                }
            }
            if (checkedNums == K && currentSum == S)
            {
                found = true;
                break;
            }
            else
            {
                checkedNums = 0;
                subsetNums.Clear();
            }
        }

        Console.WriteLine("----------------------------------");
        string arrElements = string.Join(", ", nums);
        string output = "A subset with the sum of " + S + " in the array with elements " + arrElements;
        if (found)
        {
            output += " exist.";
            output += "\r\nMembers: ";
            for (int i = 0; i < subsetNums.Count; i++)
            {
                //if (subsetNums[i] != int.MinValue)
                    output += subsetNums[i] + " ";
            }
        } else output += " does not exist.";
        Console.WriteLine(output + "\r\n");

        Console.WriteLine();
    }
}
